package org.arithmetic.other;

import javafx.beans.binding.IntegerBinding;
import javafx.beans.binding.StringBinding;

import java.util.*;

/**
 * Created by LUOLIANG on 2016/9/3.
 * 在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。
 * 给定一个整数n，请返回n位的格雷码，顺序为从0开始。   生成方法：由前一个位数少的格雷码对称生成，前（n-1）^2个每个前面加0，后（n-1）^2个每个前面加1
 * 测试样例：
 * 1   表示生成一位的格雷码
 * 返回：["0","1"]
 */
public class GrayCode {
    public static String[] getGray(int n) {
        // write code here
        String[] arr = new String[(int) Math.pow(2, n)];
        if (n == 1) {
            arr[0] = "0";
            arr[1] = "1";
        } else {
            String[] lastArr = getGray(n - 1);

            for (int i = 0; i < lastArr.length; i++) {
                arr[i] = "0" + lastArr[i];
                arr[arr.length - i - 1] = "1" + lastArr[i];
            }
        }


        return arr;
    }

    public static void main(String[] args) {
        System.out.println("请输入要生成的格雷码的位数：");
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            String[] arr = getGray(n);
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }
}
